Tổ tiên của Thổ Thổ Cáp là người bộ tộc Án Đáp Hãn Sơn ở Chiết Liên xuyên, phía bắc Vũ Bình lộ, về sau dời đến núi Ngọc Lý Ba Lý ở phía tây bắc, định cư ở đất ấy, đặt quốc hiệu là Khâm Sát. [1] Thủy tổ là Khúc Niên [2]; ông kỵ là Toa Mạt Nạp, ông cụ là Diệc Nạp Tư, đời đời làm Khâm Sát quốc vương.[3][4]

Thành Cát Tư hãn tấn công thị tộc Miệt Nhi Khất (Merkit), thủ lĩnh của họ là Hỏa Đô chạy đến Khâm Sát, được Diệc Nạp Tư che chở. Thành Cát Tư hãn sai sứ đòi giao người, Diệc Nạp Tư từ chối. Thành Cát Tư hãn mệnh cho Tốc Bất Đài, Triết Biệt đi dẹp. Diệc Nạp Tư đã già, trong nước rối loạn, ông nội của Thổ Thổ Cáp là Hốt Lỗ Tốc Man sai sứ nhận tội với Oa Khoát Đài. Đến khi Mông Ca nhận lệnh cầm quân, cha của Thổ Thổ Cáp là Ban Đô Sát đưa cả tộc đầu hàng. [3][4]

Ban Đô Sát tòng chinh Oát La Tư (Nga), tham gia chiếm thành Mạch Khiếp Tư, có công. Ban Đô Sát soái 100 người Ngọc Lý Ba Lý Khâm Sát theo Hốt Tất Liệt đánh Đại Lý, đánh Tống; bọn họ nổi tiếng cường dũng. Người Ngọc Lý Ba Lý Khâm Sát thường được hầu hạ bên cạnh Hốt Tất Liệt, coi việc nuôi ngựa, hằng năm vắt sữa ngựa dâng lên; sữa trong vắt mà vị ngon, gọi là sữa ngựa đen; tiếng Mông Cổ gọi đen là Cáp lạt, nhân đó những túc vệ người Ngọc Lý Ba Lý Khâm Sát được gọi là Cáp Lạt Xích. Hốt Tất Liệt gả em gái của chư vương Cáp Nạp là Nột Luân cho Ban Đô Sát.[3][4]